package main.二分查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/24 19:29
 * @description
 */
public class T34在排序数组中查找元素的第一个和最后一个位置 {

    public static void main(String[] args) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(searchRange(nums, 8)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int start = getPosition(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        //这个代表的是目标值为9的左边那个数
        int end = getPosition(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    /**
     * 数组里面有重复值的模板，low返回的是大于等于target的第一个数的索引下标,
     * while里面的第一个if要先判断小于符号，不然会不通过
     * 如果目标值比数组里面的所有值都大，那么low的值是数组的长度,即就是num[low]会越界，所以要做一个判断
     *
     * @param nums
     * @param target
     * @return
     */
    public static int getPosition(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) / 2);
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}
